Tree-structured macroblock partitioning is adopted in current major video coding standards. The International Telecommunication Union, Telecommunication Sector (ITU-T) H.261 Recommendation (hereinafter the “H.261 Recommendation”), the International Organization for Standardization/International Electrotechnical Commission (ISO/IEC) Moving Picture Experts Group-1 Standard (hereinafter the “MPEG-1 Standard), and the ISO/IEC Moving Picture Experts Group-2 Standard/ITU-T H.263 Recommendation (hereinafter the “MPEG-2 Standard”) support only 16×16 macroblock (MB) partitions. The ISO/IEC Moving Picture Experts Group-4 Part 2 simple profile or ITU-T H.263(+) Recommendation support both 16×16 and 8×8 partitions for a 16×16 macroblock. The MPEG-4 AVC Standard supports tree-structured hierarchical macroblock partitions. A 16×16 macroblock can be partitioned into macroblock partitions of sizes 16×8, 8×16, or 8×8. 8×8 partitions are also known as sub-macroblocks. Sub-macroblocks can be further broken into sub-macroblock partitions of sizes 8×4, 4×8, and 4×4.
Depending on whether predictive (P) Frames or bi-predictive (B) Frames are encoded, different prediction configurations are possible using the tree-based partitions. These prediction configurations define the available coding modes in the MPEG-4 AVC Standard coder and/or decoder. P frames allow for temporal prediction from a first list of reference frames, while B frames allow the use of up to two lists of reference frames, for backward/forward/bi-predictional prediction in block partitions. More generally, we will not specify any direction. Instead, P frames predict from LIST 0, B frames allow prediction from LIST 0, LIST 1 or LIST 0 and LIST 1. For simplicity, in the following text, we will simply refer to forward prediction for LIST 0 prediction, backward prediction for LIST 1 prediction, and bi-prediction for both LIST 0 and LIST 1 prediction. For instance, examples of these coding modes for P and B frames include the following:
      P    ⁢          -        ⁢    frame    ⁢          :                  MODE      ∈              {                                                                              INTRA                  ⁢                                                                          ⁢                  4                  ×                  4                                ,                                  INTRA                  ⁢                                                                          ⁢                  16                  ×                  16                                ,                                  INTRA                  ⁢                                                                          ⁢                  8                  ×                  8                                ,                SKIP                ,                                                                                                          INTER                  ⁢                                                                          ⁢                  16                  ×                  16                                ,                                  INTER                  ⁢                                                                          ⁢                  16                  ×                  8                                ,                                  INTER                  ⁢                                                                          ⁢                  8                  ×                  16                                ,                                                                                                                                                                            INTER                        ⁢                                                                                                  ⁢                        8                        ×                        8                                            ,                                              INTER                        ⁢                                                                                                  ⁢                        8                        ×                        4                                            ,                                                                                                                                                          INTER                        ⁢                                                                                                  ⁢                        4                        ×                        8                                            ,                                              INTER                        ⁢                                                                                                  ⁢                        4                        ×                        4                                                                                                                                }              ,                  ⁢          B      ⁢              -            ⁢      frame      ⁢              :                        MODE      ∈              {                                                                                                                                                INTRA                        ⁢                                                                                                  ⁢                        4                        ×                        4                                            ,                                              INTRA                        ⁢                                                                                                  ⁢                        16                        ×                        16                                            ,                                                                                                                                                          INTRA                        ⁢                                                                                                  ⁢                        8                        ×                        8                                            ,                      BIDIRECT                      ,                      DIRECT                      ,                                                                                                                                                                FWD                  ⁢                                                                          ⁢                  16                  ×                  16                                ,                                  BKW                  ⁢                                                                          ⁢                  16                  ×                  16                                ,                                  BI                  ⁢                                                                          ⁢                  16                  ×                  16                                                                                                                                                                                            FWD                        -                                                  FWD                          ⁢                                                                                                          ⁢                          16                          ×                          8                                                                    ,                                              FWD                        -                                                  BKW                          ⁢                                                                                                          ⁢                          16                          ×                          8                                                                    ,                                                                                                                                                          BKW                        -                                                  FWD                          ⁢                                                                                                          ⁢                          16                          ×                          8                                                                    ,                                              BKW                        -                                                  BKW                          ⁢                                                                                                          ⁢                          16                          ×                          8                                                                                                                                                                                                                                                                                FWD                        -                                                  BI                          ⁢                                                                                                          ⁢                          16                          ×                          8                                                                    ,                                              BI                        -                                                  FWD                          ⁢                                                                                                          ⁢                          16                          ×                          8                                                                    ,                                                                                                                                                          BKW                        -                                                  BI                          ⁢                                                                                                          ⁢                          16                          ×                          8                                                                    ,                                              BI                        -                                                  BKW                          ⁢                                                                                                          ⁢                          16                          ×                          8                                                                    ,                                              BI                        -                                                  BI                          ⁢                                                                                                          ⁢                          16                          ×                          8                                                                                                                                                                                                                                                                                FWD                        -                                                  FWD                          ⁢                                                                                                          ⁢                          8                          ×                          16                                                                    ,                                              FWD                        -                                                  BKW                          ⁢                                                                                                          ⁢                          8                          ×                          16                                                                    ,                                                                                                                                                          BKW                        -                                                  FWD                          ⁢                                                                                                          ⁢                          16                          ×                          8                                                                    ,                                              BKW                        -                                                  BKW                          ⁢                                                                                                          ⁢                          16                          ×                          8                                                                                                                                                                                                                                                                                FWD                        -                                                  BI                          ⁢                                                                                                          ⁢                          16                          ×                          8                                                                    ,                                              BI                        -                                                  FWD                          ⁢                                                                                                          ⁢                          16                          ×                          8                                                                    ,                                                                                                                                                          BKW                        -                                                  BI                          ⁢                                                                                                          ⁢                          16                          ×                          8                                                                    ,                                              BI                        -                                                  BKW                          ⁢                                                                                                          ⁢                          16                          ×                          8                                                                    ,                                              BI                        -                                                  BI                          ⁢                                                                                                          ⁢                          16                          ×                          8                                                                                                                                                                                                              8                  ×                  8                                ,                                  etc                  ⁢                                                                          ⁢                  …                                                                    }              ,  where “FWD” indicates prediction from the forward prediction list or list 0, “BKW” indicates prediction from the backward prediction list or list 1, “BI” indicates bi-prediction from both the forward and backward lists, “FWD-FWD indicates two predictions each from the forward prediction list, and “FWD-BKW” indicates a first prediction from the forward prediction list and a second prediction from the backward prediction list.
The frame partition in the MPEG-4 AVC Standard is more efficient than the simple uniform block partition typically used in older video coding standards such as MPEG-2. However, tree based frame partitioning is not without deficiency, as it is inefficient in some coding scenarios due to its inability to capture the geometric structure of two-dimensional (2D) data. In order to solve such limitations, a prior art method (hereinafter “prior art method”) was introduced to better represent and code two-dimensional video data by taking its two-dimensional geometry into account. The prior art method utilizes wedge partitions (i.e., partition of a block into two regions that are separated by an arbitrary line or curve) in a new set of modes for both inter (INTER16×16GEO, INTER8×8GEO) and intra prediction (INTRA16×16GEO, INTRA8×8GEO).
In one implementation of the prior art method, the MPEG-4 AVC Standard is used as a basis to incorporate the geometric partition mode. Geometric partitions within blocks are modeled by the implicit formulation of a line. Turning to FIG. 1, an exemplary geometric partitioning of an image block is indicated generally by the reference numeral 100. The overall image block is indicated generally by the reference numeral 120, and the two partitions of the image block 120, locating on opposing sides of diagonal line 150, are respectively indicated generally by the reference numerals 130 and 140.
Hence, partitions are defined as follows:f(x,y)=x cos θ+y sin θ−ρ,where ρ, θ respectively denote the following: the distance from the origin to the boundary line f(x,y) in the orthogonal direction to f(x,y); and the angle of the orthogonal direction to f(x,y) with the horizontal coordinate axis x.
It directly follows from its formulation that more involved models for f(x,y) with higher order geometric parameters are also considered.
Each block pixel (x,y) is classified such that:
  GEO_Partition  =      {                                                      if              ⁢                                                          ⁢                              f                ⁡                                  (                                      x                    ,                    y                                    )                                                      >            0                                                Partition            ⁢                                                  ⁢            0                                                                          if              ⁢                                                          ⁢                              f                ⁡                                  (                                      x                    ,                    y                                    )                                                      =            0                                                Line            ⁢                                                  ⁢            Boundary                                                                          if              ⁢                                                          ⁢                              f                ⁡                                  (                                      x                    ,                    y                                    )                                                      <            0                                                Partition            ⁢                                                  ⁢            1                              
For coding purposes, a dictionary of possible partitions (or geometric modes) is a priori defined. This can be formally defined such that:
                    ρ        ⁢                  :                ⁢        ρ            ∈                        [                      0            ,                                                            2                                ⁢                                  MB                  Size                                            2                                )                ⁢                                  ⁢        and        ⁢                                  ⁢        ρ            ⋐              {                  0          ,                      Δ            ⁢                                                  ⁢            ρ                    ,                                    2              ·              Δ                        ⁢                                                  ⁢            ρ                    ,                      3            ·            Δρ                    ,          …                }              ,                  ⁢    and        θ    ⁢          :        ⁢          {                                                                                                                              if                      ⁢                                                                                          ⁢                      ρ                                        =                    0                                                                                        θ                    ∈                                          [                                              0                        ,                        180                                            )                                                                                                                    else                                                                      θ                    ∈                                          [                                              0                        ,                        360                                            )                                                                                            ⁢                                                  ⁢            and            ⁢                                                  ⁢            θ                    ⋐                      {                          0              ,                              Δ                ⁢                                                                  ⁢                θ                            ,                                                2                  ·                  Δ                                ⁢                                                                  ⁢                θ                            ,                              3                ·                Δθ                            ,              …                        ⁢                                                  }                          ,            where Δρ and Δθ are the selected quantization (parameter resolution) steps. The quantized indices for θ and ρ are the information transmitted to code the edge. However, if modes 16×8 and 8×16 are used in the coding procedure, angles 0 and 90, for the case of ρ=0, can be removed from the set of possible edges.
Within the prior art method, for a geometry-adaptive motion compensation mode, a search on θ and ρ, and motion vectors for each partition is performed in order to find the best configuration. A full search strategy is done in two stages, for every θ and ρ pair, where the best motion vectors are searched. Within the geometry-adaptive intra prediction mode, a search on θ and ρ and the best predictor (directional prediction or statistics, and so forth) for each partition is performed in order to find the best configuration.
Turning to FIG. 2, an exemplary INTER-P image block partitioned with a geometry adaptive straight line is indicated generally by the reference numeral 200. The overall image block is indicated generally by the reference numeral 220, and the two partitions of the image block 220 are respectively indicated generally by the reference numerals 230 and 240.
The prediction compensation of the block can be stated as follows for P modes:Î=Ît′({right arrow over (x)}−MV1)·MASKP0(x,y)+Ît″({right arrow over (x)}−MV2)·MASKP1(x,y),where Ît represents the current prediction and Ît′({right arrow over (x)}−MV2) and Ît″({right arrow over (x)}−MV1) are the block motion compensated references for partitions P2 and P1, respectively. Each MASKP(x,y) includes the contribution weight for each pixel (x,y) for each of the partitions. Pixels that are not on the partition boundary generally do not need any operation. In practice, the mask value is either 1 or 0. Only those pixels near the partition border may need to combine the prediction values from both references.
Thus, while inter prediction using geometric adaptive block partitioning has been identified as a promising research direction on improving coding efficiency, current implementations of the same have been limited to INTER-P frames.